Network elements that forward packets in packet-switched networks typically separate their forwarding services (e.g. the tasks of moving packets from one network interface to another) from their routing services (e.g. the tasks of determining the best path through the network). For example, a network element, such as a router, typically receives a packet at one of its network interfaces and forwards the packet to another of its network interfaces. In making the decision to which network interface to forward the packet, the network element typically uses information included in the header of the packet, as well as routing information (also referred to as “routes”) stored and managed by the network element.
The routing information managed by a network element includes information about the connectivity between the nodes of the network in which the network element is established, and information about the connectivity to nodes in other networks.
For example, the routing information may include the routes to the network destinations that are reachable from the network element. A route includes an address destination, which is usually represented by an address prefix (also referred to as prefix), and information that describe the path to the address destination. The address prefix may be expressed as a combination of a network address and a mask that indicates how many bits of the address are used to identify the network portion of the address. The information that describes the path to the address destination may include, for example, the address of a node that is the next hop to the address destination, the list of Autonomous Systems (ASs) that must be traversed in order to reach the address destination, and the network address of the node that originated the route.
The routing information managed by a network element may also include information that indicates the type of each network interface of the network element, the network node or nodes that are connected to the network element over each network interface, and various other parameters that may be associated with the network element or its network interfaces.
A network element that separates its forwarding service from its routing service typically stores all of its routing information in a Routing Information Base (RIB). Each routing protocol that executes on the network element selects its own set of best routes, and installs those routes and their attributes in the RIB. Within a routing protocol, the routes are selected based on one or more criteria, or metrics, used by that protocol. A RIB process periodically traverses the routes in the RIB and selects the best overall route to each address destination by comparing the attributes of ail routes to that destination. The routes identified in the RIB as best routes are then transferred, or downloaded, to one or more Forwarding information Bases (FIBs) that are used for forwarding packets by the one or more network interlaces of the network element. Thus, at any given point in time a FIB maintains an image of all or a subset of the routing information contained in the RIB. When routing or topology changes occur in the network, the routing information in the RIB is updated and the changes to the routing information are reflected in the one or more FIBs.
Network elements may store the routing information in the RIB as one or more logically or physically separate routing tables to facilitate orderly management of different services. For example, a network element that supports Virtual Private Network (VPN) features usually manages the routes of different VPNs in separate logical or physical routing tables. In another example, a network element may manage routes for different topologies, such as, for example, topologies associated with a different Quality of Service (QoS), in separate routing tables. Further, a plurality of network elements may execute as a virtual router, and each network element in the virtual router may store the RIBs of the other network elements of the virtual router in logically or physically separate routing tables.
Routes that are no longer reachable or viable (stale) need to be removed from the various RIBs and the FIB. Because routing processes update only the reachable routes, not the stale routes, the stale routes are discovered by separate burdensome processes. For example, after all active routes have been computed and stored in an updated routing table, each route entry in the updated routing table cars be compared to each entry in the old routing table to identify new routes, changed routes, unchanged routes, and stale routes. Stale routes are routes that exist in the old routing table and not in the updated routing table.
Comparing every route in the updated routing table and old routing table can create a significant burden on the computational resources of the network element and can be especially wasteful when only a few routes have become stale from one routing computation cycle to another.